home *** CD-ROM | disk | FTP | other *** search
/ PsL Monthly 1993 December / PSL Monthly Shareware CD-ROM (December 1993).iso / prgmming / dos / pascal / qksort.com / QKSORT.DOC < prev    next >
Encoding:
Text File  |  1990-02-14  |  6.7 KB  |  188 lines
  1. QKSORT Documentation
  2. --------------------
  3.  
  4. QKSORT is a small unit for Turbo Pascal 5.0 that implements two routines
  5. similar to ones found in the Turbo C library: qsort and bsearch.
  6.  
  7. qsort performs in-memory sorting of an array with the Quicksort algorithm.
  8. arrays of any type, up to a maximum of 32767 elements, may be sorted.
  9.  
  10. bsearch performs a binary search of an array.  The array must be in sorted
  11. order, and may be of any type, up to a maximum of 32767 elements.
  12.  
  13. As in the Turbo C functions, qsort and bsearch are "engines" which rely on
  14. a user-written comparison function to determine the proper sort sequence.
  15. This gives you tremendous flexibility, because you don't need a separate
  16. sort or search routine for each data structure.  Only the comparison
  17. function needs to change.
  18.  
  19.  
  20. Defining the comparison function
  21. --------------------------------
  22.  
  23. Your comparison function MUST be written with the following format:
  24.  
  25.    {$F+}                                { must be a far call }
  26.    function mycomp(var p1,p2) : integer;
  27.  
  28.    begin
  29.       ...
  30.       mycomp := ...
  31.    end;
  32.    {$F-}
  33.  
  34. You may use any function name you wish, but it MUST be a far function
  35. {$F+}, it MUST have two untyped var parameters (p1 and p2), and it MUST
  36. return an integer.
  37.  
  38. The comparison function must return an integer based on the sequence of the
  39. two records:
  40.  
  41.    <0  record p1 comes BEFORE record p2 in sequence
  42.     0  record p1 and record p2 are equivalent in terms of sequence
  43.    >0  record p1 comes AFTER record p2 in sequence
  44.  
  45.  
  46. Using qsort
  47. -----------
  48.  
  49. Usually, you will be sorting or searching on arrays of records.  Here is an
  50. example showing how a comparsion function would be written.  Suppose you
  51. have a mailing list that you want to sort in ascending order of last name:
  52.  
  53.    uses
  54.       qksort;
  55.  
  56.    type
  57.       mail_rec      = record            { mailing list record }
  58.                          id    : integer;         { ID number }
  59.                          lname : string[24];      { last name }
  60.                          fname : string[12];      { first name }
  61.                          .
  62.                          .  (additional fields in record)
  63.                          .
  64.                       end;
  65.  
  66.    var
  67.       mail_list     = array[0..100] of mail_rec;
  68.  
  69.  
  70.    function mail_comp(var p1,p2) : integer;
  71.  
  72.    { comparison function to sort mailing list in ascending order of
  73.      last name. }
  74.  
  75.    begin
  76.       if mail_rec(p1).lname < mail_rec(p2).lname then
  77.          mail_comp := -1
  78.       else if mail_rec(p1).lname > mail_rec(p2).lname then
  79.          mail_comp := 1
  80.       else
  81.          mail_comp := 0;
  82.    end;
  83.  
  84.  
  85. Notice the use of "mail_rec(p1)".  This typecasting is necessary so that
  86. Turbo can figure out the type of the variables being compared, since they
  87. are passed as untyped parameters.
  88.  
  89. Notice also that this function could easily be changed to sort on a
  90. different field, or to sort in descending order instead of ascending order.
  91.  
  92. Now, to actually sort the records, assuming the number of actual records
  93. in the array is in the variable numrec, the call is:
  94.  
  95.    qsort(mail_list,nr,sizeof(mail_rec),mail_comp);
  96.  
  97. You should always use the sizeof() function to pass the record size.  In
  98. that way, if you ever change the record structure, your sort call will
  99. not need to be modified.
  100.  
  101.  
  102. Using bsearch
  103. -------------
  104.  
  105. bsearch performs a binary search on a sorted array for a given key value.
  106. Note that the array must be sorted; otherwise bsearch will not work
  107. properly.
  108.  
  109. The call to bsearch is similar to the call to qsort, except that you need
  110. to specify the key value as the first parameter.  Using the example above,
  111. if you wanted to search for a key value stored in the variable k, the call
  112. would be:
  113.  
  114.    i := bsearch(k,mail_list,nr,sizeof(mail_list),mail_comp);
  115.  
  116. The function returns either a record number (starting at 0) if the key was
  117. found, or -1 if the key was not found.  (Note: this is different that the
  118. Turbo C function return of a pointer.)
  119.  
  120. IMPORTANT NOTE:  bsearch does not care what the type of the key value is.
  121. It is the responsibility of the comparison function to know that the SECOND
  122. parameter passed is the key value, while the first parameter is a record.
  123. This leaves you with two choices:
  124.  
  125. Method 1 is to pass a simple key value (a string in the example shown), in
  126. which case the comparison function must be aware that the two parameters
  127. being passed are of different types.
  128.  
  129. Method 2 is to pass an entire record of the same type as the array being
  130. searched.  This record only needs to have the key value set.  The advantage
  131. of method 2 is that you can use the same comparison function for both qsort
  132. and bsearch.
  133.  
  134. Using method 2 on the example above, the value k would have been defined
  135. as:
  136.  
  137.    var
  138.       k             : mail_rec;         { a single record }
  139.  
  140.    .
  141.    .
  142.    .
  143.  
  144.    k.lname := 'Schwartz';               { the key I'm looking for }
  145.    i := bsearch(k,mail_list,nr,sizeof(mail_list),mail_comp);
  146.  
  147.  
  148. Good luck with these routines.  I hope you find them useful.
  149.  
  150.    -- Bob Showalter
  151.       CompuServe ID 72220,466
  152.  
  153.  
  154.          ----------------end-of-author's-documentation---------------
  155.  
  156.                         Software Library Information:
  157.  
  158.                    This disk copy provided as a service of
  159.  
  160.                         The Public (Software) Library
  161.  
  162.          We are not the authors of this program, nor are we associated
  163.          with the author in any way other than as a distributor of the
  164.          program in accordance with the author's terms of distribution.
  165.  
  166.          Please direct shareware payments and specific questions about
  167.          this program to the author of the program, whose name appears
  168.          elsewhere in  this documentation. If you have trouble getting
  169.          in touch with the author,  we will do whatever we can to help
  170.          you with your questions. All programs have been tested and do
  171.          run.  To report problems,  please use the form that is in the
  172.          file PROBLEM.DOC on many of our disks or in other written for-
  173.          mat with screen printouts, if possible.  The P(s)L cannot de-
  174.          bug programs over the telephone.
  175.  
  176.          Disks in the P(s)L are updated monthly, so if you did not get
  177.          this disk  directly from the P(s)L,  you should be aware that
  178.          the files in this set may no  longer be the current versions.
  179.  
  180.          For a copy of the latest monthly software library newsletter
  181.          and a list of the 2,000+ disks in the library, call or write
  182.  
  183.                         The Public (Software) Library
  184.                               P.O.Box 35705
  185.                            Houston, TX 77235-5705
  186.                                (713) 524-6394
  187.  
  188.